home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / ps_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  5.0 KB  |  205 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  ps_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_PSTREE_H
  17. #define LEDA_PSTREE_H
  18.  
  19. //--------------------------------------------------------------------
  20. //  
  21. //  Priority Search Trees
  22. //
  23. //  Renate Lassen (1990)
  24. //
  25. // Implementation as described in
  26. // Kurt Mehlhorn: Data Structures and Algorithms 2, section III.5.1.2
  27. //
  28. //--------------------------------------------------------------------
  29.  
  30. // -----------------------------------------------------
  31. // includes
  32. // -----------------------------------------------------
  33.  
  34. #include <LEDA/basic.h>
  35. #include <LEDA/b_stack.h>
  36.  
  37.  
  38. // -----------------------------------------------------
  39. // declarations and definitions
  40. // -------------------------------------------------------
  41.  
  42. const BSTACKSIZE = 70 ; // according to tree.size and alpha
  43.                  // here: tree.size <= 10^9
  44.                  //       alpha = 0.25 ( worst case )
  45.  
  46. enum children     { left = 0 , right = 1 };
  47. enum leaf_or_node { leaf = 0 , node = 1 } ;
  48.  
  49. class ps_node;
  50. class ps_tree;
  51.  
  52. typedef int x_typ;
  53. typedef ps_node* ps_item;
  54.  
  55. struct pair { x_typ x_pkt;
  56.               x_typ y_pkt;
  57.               bool valid;
  58.             };
  59.  
  60. typedef pair* pair_item;
  61.  
  62.  
  63. // -------------------------------------------------------
  64. // class ps_node     
  65. // -------------------------------------------------------
  66.  
  67. class ps_node {
  68.  
  69.   x_typ x_val;
  70.   x_typ y_val;
  71.   x_typ split_val[2];
  72.   int gr;
  73.   ps_item sohn[2];
  74.  
  75.   friend class ps_tree;
  76.  
  77. public:
  78.  
  79.   x_typ x_value()           { return x_val; }
  80.   x_typ y_value()           { return y_val; }
  81.   x_typ split_value_x()     { return split_val[0]; }
  82.   x_typ split_value_y()     { return split_val[1]; }
  83.  
  84.   int blatt()             { return (gr==1); }
  85.   int groesse()           { return gr; }
  86.  
  87.  
  88.   float bal()
  89.   { if (blatt()) return 0.5;
  90.     else return float(float(sohn[left]->groesse())/float(gr));
  91.    }
  92.  
  93.  
  94.   ps_node(x_typ x_v=0,x_typ y_v=0,x_typ split_v_0=0,x_typ split_v_1=0,leaf_or_node ln=leaf,ps_item ls=0,ps_item rs=0)
  95.     { x_val = x_v;
  96.       y_val = y_v;
  97.       split_val[0] = split_v_0;
  98.       split_val[1] = split_v_1;
  99.       sohn[left] = ls;
  100.       sohn[right] = rs;
  101.       if (ln==leaf)
  102.     gr=1;
  103.       else gr = ls->groesse()+rs->groesse();
  104.     }
  105.  
  106.   ps_node(ps_item p)
  107.     { x_val = p->x_value();
  108.       y_val = p->y_value();
  109.       split_val[0] = p->split_value_x();
  110.       split_val[1] = p->split_value_y();
  111.       gr = p->groesse();
  112.       sohn[left] = p->sohn[left];
  113.       sohn[right] = p->sohn[right];
  114.     }
  115.  
  116.   LEDA_MEMORY(ps_node)
  117.       
  118. }; 
  119.  
  120.  
  121. // -------------------------------------------------------
  122. // class ps_tree     
  123. // -------------------------------------------------------
  124.  
  125. class ps_tree {
  126.  
  127.   ps_item root;
  128.   int   anzahl; 
  129.   float alpha;
  130.   float d;
  131.   b_stack<ps_item> st;
  132.  
  133.   friend class ps_node;
  134.  
  135.   void  lrot(ps_item , ps_item ); 
  136.   void  rrot(ps_item , ps_item ); 
  137.   void  ldrot(ps_item , ps_item ); 
  138.   void  rdrot(ps_item , ps_item ); 
  139.  
  140.   ps_item sink(ps_item, x_typ , x_typ);
  141.   void fill(ps_item);
  142.   void delleaf(ps_item);
  143.   void deltree(ps_item);
  144.    
  145.   ps_item search(x_typ, x_typ);
  146.   ps_item locate(x_typ, x_typ);
  147.  
  148.   void enumerate(x_typ, x_typ, x_typ, ps_item);
  149.   void pr_ps_tree(ps_item, int);
  150.   pair_item min_x_in_rect(x_typ ,x_typ ,x_typ ,ps_item);
  151.   pair_item max_x_in_rect(x_typ ,x_typ ,x_typ ,ps_item);
  152.   pair_item min_y_in_xrange(x_typ ,x_typ ,ps_item);
  153.  
  154. public:
  155.  
  156.   virtual int cmp(x_typ x,x_typ y) { return int(x)-int(y); }
  157.   virtual int cmp(x_typ x1,x_typ y1,x_typ x2,x_typ y2) 
  158.                                    { if (int(x1)==int(x2))
  159.                                         return int(y1)-int(y2); 
  160.                                      else return int(x1)-int(x2); }
  161.  
  162.   x_typ   x_value(ps_item it)      { return (it) ? it->x_value() : 0 ; }
  163.   x_typ   y_value(ps_item it)      { return (it) ? it->y_value() : 0 ; }
  164.   x_typ   split_value_x(ps_item it)  { return (it) ? it->split_value_x() : 0 ; }
  165.   x_typ   split_value_y(ps_item it)  { return (it) ? it->split_value_y() : 0 ; }
  166.  
  167.   ps_item insert(x_typ ,x_typ );
  168.   ps_item del(x_typ ,x_typ );
  169.      
  170.   pair_item min_x_in_rect(x_typ x1,x_typ x2,x_typ y0) 
  171.                          { return min_x_in_rect(x1,x2,y0,root); }
  172.   pair_item max_x_in_rect(x_typ x1,x_typ x2,x_typ y0)
  173.                          { return max_x_in_rect(x1,x2,y0,root); }
  174.   pair_item min_y_in_xrange(x_typ x1,x_typ x2)
  175.                            { return min_y_in_xrange(x1,x2,root); }
  176.  
  177.   void enumerate(x_typ x1,x_typ x2,x_typ y0) { enumerate(x1,x2,y0,root); }
  178.  
  179.   void pr_ps_tree() { pr_ps_tree(root,0); }
  180.  
  181.   ps_tree()   :  st(BSTACKSIZE) 
  182.   { root = 0;
  183.     anzahl = 0;
  184.     alpha=0.28;
  185.     d=1/(2-alpha);
  186.    }
  187.  
  188.   virtual ~ps_tree()  
  189.   { if (root)
  190.     { deltree(root);
  191.       delete(root);
  192.      } 
  193.     root = 0; 
  194.     anzahl = 0;
  195.     alpha = 0;
  196.     d = 0;
  197.    }
  198.  
  199. };
  200.  
  201.  
  202. //------------------------------------------------------------------
  203.  
  204. #endif
  205.